#include<stdio.h>
#include<stdlib.h>
using namespace std;
#define maxsize 10
#define INF 65535
typedef struct agraph{
    char vex[maxsize];
    int edges[maxsize][maxsize];
    int n;
}*graph;
void Floyd(graph g,int dist[][maxsize],int path[][maxsize]){
    int i,j,k;
    for(i=0;i<g->n;i++){//初始化
        for(j=0;j<g->n;j++){
            dist[i][j]=g->edges[i][j];
            path[i][j]=j;
        }
    }
    for(k=0;k<g->n;k++){//找一个中间结点
        for(i=0;i<g->n;i++){
            for(j=0;j<g->n;j++){
                if(dist[i][j]>dist[i][k]+dist[k][j]){
                    dist[i][j]=dist[i][k]+dist[k][j];
                    path[i][j]=path[i][k];//按顺序存i->j途径的k
                }
            }
        }
    }
}
void fun(graph g){
    int dist[maxsize][maxsize];
    int path[maxsize][maxsize];
    Floyd(g,dist,path);
    int i,j,max=0;
    int u,v;
    for(i=0;i<g->n;i++){
        for(j=0;j<g->n;j++){
            if(max<dist[i][j]){
                max=dist[i][j];
                u=i;
                v=j;
            }
        }
    }
    //求最大的最小路径
    printf("%c -> %c 的最大的最小路径为：%d\n", g->vex[u], g->vex[v], dist[u][v]);
    printf("path: %c", g->vex[u]);//打印起点
    int k = path[u][v];
    while(k != v){
        printf("-> %c", g->vex[k]);//打印中间点
        k = path[k][v]; 
    }
    printf("-> %c\n", g->vex[v]);
}
int main(){
    graph g=(graph)malloc(sizeof(struct agraph));
    char arrv[maxsize]={'a','b','c','d','e','f','g'};
    int arre[][maxsize]={
        {0,12,INF,INF,INF,16,14},
		{12,0,10,INF,INF,7,INF},
		{INF,10,0,3,5,6,INF},
		{INF,INF,3,0,4,INF,INF},
		{INF,INF,5,4,0,2,8},
		{16,7,6,INF,2,0,9},
		{14,INF,INF,INF,8,9,0}
    };
    g->n=7;
    for(int i=0;i<g->n;i++){
        g->vex[i]=arrv[i];
    }
    for(int i=0;i<g->n;i++){
        for(int j=0;j<g->n;j++){
            g->edges[i][j]=arre[i][j];
        }
    }
    fun(g);
    return 0;
}